/*
https://leetcode-cn.com/problems/valid-parenthesis-string/solution/you-xiao-de-gua-hao-zi-fu-chuan-by-leetc-osi3/
 */

public class Solution678 {
    public boolean checkValidString(String s) {
        int max=0,min=0;
        for (int i=0;i<s.length();i++){
            if (s.charAt(i)=='('){
                max++;min++;
            }
            if (s.charAt(i)==')'){
                max--;
                if (max<0){
                    return false;
                }
                min=Math.max(min-1,0);
            }
            if (s.charAt(i)=='*'){
                max++;
                min=Math.max(min-1,0);
            }
        }
        return min==0?true:false;
    }

    public static void main(String[] args) {
        System.out.println(new Solution678().checkValidString("(*)"));
    }
}
